package com.jiangxun.leetcode.editor.cn;//<p>你可以选择使用单链表或者双链表，设计并实现自己的链表。</p>
//
//<p>单链表中的节点应该具备两个属性：<code>val</code> 和 <code>next</code> 。<code>val</code> 是当前节点的值，<code>next</code> 是指向下一个节点的指针/引用。</p>
//
//<p>如果是双向链表，则还需要属性&nbsp;<code>prev</code>&nbsp;以指示链表中的上一个节点。假设链表中的所有节点下标从 <strong>0</strong> 开始。</p>
//
//<p>实现 <code>MyLinkedList</code> 类：</p>
//
//<ul> 
// <li><code>MyLinkedList()</code> 初始化 <code>MyLinkedList</code> 对象。</li> 
// <li><code>int get(int index)</code> 获取链表中下标为 <code>index</code> 的节点的值。如果下标无效，则返回 <code>-1</code> 。</li> 
// <li><code>void addAtHead(int val)</code> 将一个值为 <code>val</code> 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。</li> 
// <li><code>void addAtTail(int val)</code> 将一个值为 <code>val</code> 的节点追加到链表中作为链表的最后一个元素。</li> 
// <li><code>void addAtIndex(int index, int val)</code> 将一个值为 <code>val</code> 的节点插入到链表中下标为 <code>index</code> 的节点之前。如果 <code>index</code> 等于链表的长度，那么该节点会被追加到链表的末尾。如果 <code>index</code> 比长度更大，该节点将 <strong>不会插入</strong> 到链表中。</li> 
// <li><code>void deleteAtIndex(int index)</code> 如果下标有效，则删除链表中下标为 <code>index</code> 的节点。</li> 
//</ul>
//
//<p>&nbsp;</p>
//
//<p><strong class="example">示例：</strong></p>
//
//<pre>
//<strong>输入</strong>
//["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
//[[], [1], [3], [1, 2], [1], [1], [1]]
//<strong>输出</strong>
//[null, null, null, null, 2, null, 3]
//
//<strong>解释</strong>
//MyLinkedList myLinkedList = new MyLinkedList();
//myLinkedList.addAtHead(1);
//myLinkedList.addAtTail(3);
//myLinkedList.addAtIndex(1, 2);    // 链表变为 1-&gt;2-&gt;3
//myLinkedList.get(1);              // 返回 2
//myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1-&gt;3
//myLinkedList.get(1);              // 返回 3
//</pre>
//
//<p>&nbsp;</p>
//
//<p><strong>提示：</strong></p>
//
//<ul> 
// <li><code>0 &lt;= index, val &lt;= 1000</code></li> 
// <li>请不要使用内置的 LinkedList 库。</li> 
// <li>调用 <code>get</code>、<code>addAtHead</code>、<code>addAtTail</code>、<code>addAtIndex</code> 和 <code>deleteAtIndex</code> 的次数不超过 <code>2000</code> 。</li> 
//</ul>
//
//<div><div>Related Topics</div><div><li>设计</li><li>链表</li></div></div><br><div><li>👍 1067</li><li>👎 0</li></div>

//leetcode submit region begin(Prohibit modification and deletion)

class ListNode {
    int val;
    ListNode next;
    ListNode prev;

    ListNode() {}

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    ListNode(int val, ListNode next, ListNode prev) { // 构造函数新增 prev 参数
        this.val = val;
        this.next = next;
        this.prev = prev;
    }
}

class MyLinkedList {

    //记录链表中元素的数量
    int size;
    //记录链表的虚拟头结点和尾结点
    ListNode head,tail;

    public MyLinkedList() {
        //初始化操作
        this.size = 0;
        this.head = new ListNode(0);
        this.tail = new ListNode(0);
        //这一步非常关键，否则在加入头结点的操作中会出现null.next的错误！！！
        head.next=tail;
        tail.prev=head;
    }

    public int get(int index) {
        //判断index是否有效
        if(index>=size){
            return -1;
        }
        ListNode cur = this.head;
        //判断是哪一边遍历时间更短
        if(index >= size / 2){
            //tail开始
            cur = tail;
            for(int i=0; i< size-index; i++){
                cur = cur.prev;
            }
        }else{
            for(int i=0; i<= index; i++){
                cur = cur.next;
            }
        }
        return cur.val;
    }

    public void addAtHead(int val) {
        //等价于在第0个元素前添加
        addAtIndex(0,val);
    }

    public void addAtTail(int val) {
        //等价于在最后一个元素(null)前添加
        addAtIndex(size,val);
    }

    public void addAtIndex(int index, int val) {
        //index大于链表长度
        if(index>size){
            return;
        }

        size++;
        //找到前驱
        ListNode pre = this.head;
        for(int i=0; i<index; i++){
            pre = pre.next;
        }
        //新建结点
        ListNode newNode = new ListNode(val);
        newNode.next = pre.next;
        pre.next.prev = newNode;
        newNode.prev = pre;
        pre.next = newNode;

    }

    public void deleteAtIndex(int index) {
        //判断索引是否有效
        if(index>=size){
            return;
        }
        //删除操作
        size--;
        ListNode pre = this.head;
        for(int i=0; i<index; i++){
            pre = pre.next;
        }
        pre.next.next.prev = pre;
        pre.next = pre.next.next;
    }
}
/*

class MyLinkedList {

    int size;
    */
/**
     * 虚拟头节点
     *//*

    ListNode dummyHead;

    */
/**
     * 初始化链表
     *//*

    public MyLinkedList() {
        size = 0;
        dummyHead = new ListNode();
    }

    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        ListNode curNode = dummyHead;
        //包含虚拟头节点，找index+1个节点
        for (int i = 0; i < index + 1; i++) {
            curNode = curNode.next;
        }
        return curNode.val;
    }

    public void addAtHead(int val) {
        ListNode newNode=new ListNode(val);
        //先处理后面一条线，在处理前面的线
        newNode.next=dummyHead.next;
        dummyHead.next=newNode;
        size++;
    }

    public void addAtTail(int val) {
        ListNode newNode=new ListNode(val);
        //找到尾节点
        ListNode cur=dummyHead;
        while(cur.next!=null){
            cur = cur.next;
        }
        cur.next=newNode;
        size++;
    }

    */
/**
     * addAtIndex(0, int val) 头插
     * addAtIndex(size, int val) 尾插
     * index>size，返回-1
     *//*

    public void addAtIndex(int index, int val) {
        if(index>size){
            return;
        }
        if(index<0){
            return;
        }
        //找到前驱节点
        ListNode predNode=dummyHead;
        for (int i=0;i<index;i++){
            predNode=predNode.next;
        }
        //创建待插入的新结点
        ListNode toAddNode=new ListNode(val);
        //先处理后一根线，再处理前面一个线
        toAddNode.next=predNode.next;
        predNode.next=toAddNode;
        //长度加一
        size++;
    }

    public void deleteAtIndex(int index) {
        if(index<0||index>=size){
            return;
        }
        //有虚拟头节点，不用考虑index=0；
        ListNode predNode=dummyHead;
        //找到前驱接节点
        for(int i=0;i<index;i++){
            predNode=predNode.next;
        }
        predNode.next=predNode.next.next;
        size--;
    }
}
*/

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */
//leetcode submit region end(Prohibit modification and deletion)
